\chapter{Principaux algorithmes}

	\section{Algorithme d'Euclide étendu}

		\begin{algo}
			On veut obtenir des coefficients de Bézout pour les deux polynômes A et B.
			On définit trois suites $(r_{n},s_{n},t_{n})$ telles que $\forall n$ $ r_{n} = s_{n}A + t_{n}B $.
			On a les relations de récurrence à deux éléments suivantes :
			\begin{eqnarray*}
				r_{n+1} &=& r_{n-1} - (r_{n-1} \ div \ r_{n})r_{n} \\
				s_{n+1} &=& s_{n-1} - (r_{n-1} \ div \ r_{n})s_{n} \\
				t_{n+1} &=& t_{n-1} - (r_{n-1} \ div \ r_{n})t_{n} 
			\end{eqnarray*}
			Ces relations de récurrence conservent bien la propriété, avec $(deg(r_{n}))_{n}$ suite strictement décroissante.
			Comme vu durant la démonstration du décodage, le calcul du PGCD ne nous intéresse même pas.
			On coupe l’exécution de l'algorithme dès que $deg(r_{n}) < \frac{t}{2}$.
			Pour l'initialisation on pose :
			\begin{eqnarray*}
				(r_{0},s{0},t{0}) &=& (A,1,0) \\
				(r_{1},s{1},t{1}) &=& (B,0,1) 
			\end{eqnarray*}
		\end{algo}

	\section{Pivot de Gauss et applications}

		L'algorithme du pivot de Gauss fait partie du programme de Sup.
		Nous ne redonnons ni une preuve du résultat ni un algorithme complet.
		Nous l'avons utilisé pour calculer des inverses mais nous l'avons aussi modifié pour d'autres utilisations.

		\subsection{Pivot de Gauss modifié}

			Toutes nos sources montrent comment générer une matrice de parité pour un code de Goppa.
			Cependant le cryptosystème classique de Mc Eliece utilise des matrices génératrices.
			Pour passer de l'un à l'autre nous avons utilisé un pivot de Gauss modifié.

			Les deux principales augmentations sont de permettre d'effectuer les calculs même si la matrice n'est pas inversible et de stocker les permutations effectuées dans une pile.
			Cela donne un algorithme tel que le suivant.

			\begin{algo}
				Soit M une matrice de taille n+1.
				\begin{enumerate}
					\item On cherche une ligne i dont le premier coefficient est non nul
					\item Si un tel i existe, on échange la première ligne et la i ieme ligne et on stocke cette permutation
					\item S'il n'existe pas de tel i, on cherche un (i,j) tel que $ M_{i,j}\neq 0 $, on échange la i eme ligne avec la première et la j i eme colonne avec la première en stockant ces permutations
					\item S'il n'existe pas de tel (i,j) on arrête l'algorithme, cette étape se produit toujours en pratique.
					\item On multiplie la première ligne pour avoir un premier coefficient 1
					\item $ \forall i \geq 2, l_{i} \leftarrow  l_{i} - M_{i,1} \times l_{1}$
					\item On itère pour le bloc inférieur droit de taille n
				\end{enumerate}
			\end{algo}

			On n'utilise jamais cette version du pivot de Gauss sur une matrice inversible.
			Le résultat intéressant est la pile des permutations qui permet de réorganiser, par les permutations, la matrice M comme suit :
			$$
			M = 
			\begin{pmatrix}
				A & X \\
				Y & Z
			\end{pmatrix}
			$$
			Où $A \in GL_{r}(\mathbb{F})$ avec r rang de M.

		\subsection{Construire la matrice génératrice à partir de la matrice de parité}

			C'est une des deux principales applications du pivot de Gauss modifié.
			Soit H matrice de parité, $ H \in M_{n,k}(\mathbb{F}) $.
			On cherche $G \in M_{k,n}(\mathbb{F}) $ de rang maximal telle que $HG=0$.

			Pour cela on utilise l'algorithme pour se ramener au cas de $H' = LHC$.
			$L \in GL_{n}(\mathbb{F})$ représente les permutations de lignes et $C \in GL_{k}(\mathbb{F}) $ de colonnes.
			On a donc :
			$$
			H' = 
			\begin{pmatrix}
				U & V \\
				W & Z
			\end{pmatrix}
			,
			G' = 
			\begin{pmatrix}
				X\\
				I_{n-r}
			\end{pmatrix}
			$$
			Où U est inversible de taille $r = rang( H')$.
			On veut $rang(G) = dim(Ker(H)) = n - r$ d'où le découpage de G.
			$$
			H'G' = 
			\begin{pmatrix}
				UX + V\\
				WX + Z
			\end{pmatrix}
			= 0
			$$
			On se retrouve avec un système de rang r, il suffit de poser $X = -U^{-1}V$.

			Maintenant qu'on a construit G' tel que $LHCG' = 0$, avec L et C inversibles.
			La matrice génératrice est la matrice :
			$$ G = CG'$$
			

		\subsection{Inverse à gauche d'une matrice non carrée}

			C'est ici la deuxième application.
			Après avoir corrigé les erreurs, on se retrouve avec un mot $y = Gx \in \mathbb{F}^{n}$.
			On aimerait pouvoir calculer un inverse à gauche de G nommé D. Normalement G est de rang n-r égal à son nombre de colonnes.

			On procède de même que ci-dessus avec :
			$$
			D' = 
			\begin{pmatrix}
				U^{-1} & 0_{r}
			\end{pmatrix},
			G' = LGC =
			\begin{pmatrix}
				U \\
				V
			\end{pmatrix}
			$$
			On a donc $D'LGC=I_{n-r}$.
			Pour avoir la matrice de décodage on pose :
			$$ D = C^{-1}D'L$$




	\section{Algorithme de Berlekamp-Hensel} 

		\cite{berlekamp}
		Pour générer un code de Goppa aléatoire, il faut un polynôme de $ \mathbb{F}_{2^{m}}[X] $ de degré t irréductible.
		Nous avons utilisé l'algorithme de Berlekamp pour tester l'irréductibilité d'un polynôme dans un corps fini.
		Il est plus simple à démontrer que sa version utilisée pour factoriser ces polynômes.
		Nous en donnons ici le principe et quelques morceaux de démonstration.

		\begin{prop}
			Soit $H \in \mathbb{F}_{2^{m}}[X]$, 
			$$H^{2^{m}} - H = \prod_{c \in \mathbb{F}_{2^{m}-1}}(H-c)$$
		\end{prop}
		En effet,
		$$ \forall c \in \mathbb{F}_{2^{m}}, H^{2^{m}}-H = H(H^{2^{m}-1}-1) = H(H^{2^{m}-1}-c^{2^{m}-1})$$
		Une formule que l'on a déjà utilisée montre que H-c divise le polynôme de droite.
		Comme les H-c sont premiers entre eux deux à deux et divisent $ H^{2^{m}} -H $, leur produit le divise.
		L'égalité vient de l'égalité du degré et du premier coefficient.

		Maintenant on veut tester l'irréductibilité d'un polynôme P unitaire sans facteur multiple.
		\begin{prop}
			Si $H \in \mathbb{F}_{2^{m}}[X]$ unitaire satisfait $H^{2^{m}} = H \ mod(P)$, alors 
			$$P = \prod_{c\in \mathbb{F}_{2^{m}}}pgcd(P,H-c)$$
		\end{prop}

		Pour le montrer on utilise la propriété précédente.
		P divise $H^{2^{m}} - H$ donc $P = pgcd(P,\prod(H-c))$.
		Les H-c étant premiers entre eux deux à deux, P divise le produit des PGCD.
		De plus chacun des $pgcd(P,H-c)$ divise P et ils sont premiers deux à deux donc leur produit divise P.
		Les deux polynômes étant unitaires l'égalité est satisfaite.

		On remarque que si $0<deg(H) <t$, pgcd(P,H-c) ne vaut jamais P, donc met en évidence que P n'est pas irréductible.
		On en conclut donc que l'existence de H  de degré $\in 2..t-1$ implique que P est réductible.
		Il reste à montrer l'équivalence.

		\begin{prop}
			Soit $P = P_{1} \times ... \times P_{r}$.
			D'après le théorème des restes chinois, $H \rightarrow (H \ mod(P_{1}),...H \ mod(P_{r}))$ de $\mathbb{F}[X]/P \rightarrow (\mathbb{F}[X]/P_{1},...,\mathbb{F}[X]/P_{r})$ est un isomorphisme d'anneaux.

			Comme les $P_{i}$ sont irréductibles, $\{x \in \mathbb{F}[X]/P_{1}/ x = x^{2{m}} \}$ est de cardinal $2^{m}$.
			Donc il existe $2^{mr}$ polynômes de degrés inférieurs à t-1 vérifiant la propriété désirée.
			Par suite si P est réductible il existe au moins un polynôme H avec $1 < deg(H) < t$ et $H^{2^{m}} = H \ mod(P)$.
			On a donc l'équivalence voulue.
		\end{prop}

		Maintenant qu'on a une équivalence sympatique entre l'irréductibilité de P et la non existence du polynôme H, on utilise le morphisme de Frobenius.
		C'est à dire que l'application suivante est linéaire.
		\begin{eqnarray*}
			\mathbb{F}_{2^{m}}/P &\rightarrow& \mathbb{F}_{2^{m}}/P \\
			H &\rightarrow& H^{2^{m}}
		\end{eqnarray*}

		On en déduit l'algorithme suivant :
		\begin{algo}
			Soit P de degré t dont on veut tester l'irréductibilité :
			\begin{enumerate}
				\item Si $pgcd(P,P') \neq 0$ alors P possède des facteurs multiples, à fortiori P est réductible, on arrête l’exécution.
				\item On calcule A la matrice du morphisme de Frobenius dans la base canonique
				\item On détermine le noyau de (A - Id) dans la base canonique
				\item Si $dim(Ker(A-Id)) = 1$ alors les seuls H existant sont de degré 1 et P est irréductible
				\item Sinon P est réductible
			\end{enumerate}
		\end{algo}